{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Total Cost to Make Arrays Unequal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTotalCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #让数组不相等的最小总代价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums1</code>&nbsp;和&nbsp;<code>nums2</code>&nbsp;，两者长度都为&nbsp;<code>n</code>&nbsp;。</p>\n",
    "\n",
    "<p>每次操作中，你可以选择交换 <code>nums1</code>&nbsp;中任意两个下标处的值。操作的 <strong>开销</strong>&nbsp;为两个下标的 <strong>和</strong>&nbsp;。</p>\n",
    "\n",
    "<p>你的目标是对于所有的 <code>0 &lt;= i &lt;= n - 1</code>&nbsp;，都满足&nbsp;<code>nums1[i] != nums2[i]</code>&nbsp;，你可以进行 <strong>任意次</strong>&nbsp;操作，请你返回达到这个目标的 <strong>最小</strong>&nbsp;总代价。</p>\n",
    "\n",
    "<p>请你返回让<em>&nbsp;</em><code>nums1</code> 和&nbsp;<code>nums2</code><em>&nbsp;</em>满足上述条件的 <strong>最小总代价</strong> ，如果无法达成目标，返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>\n",
    "实现目标的其中一种方法为：\n",
    "- 交换下标为 0 和 3 的两个值，代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。\n",
    "- 交换下标为 1 和 2 的两个值，代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。\n",
    "- 交换下标为 0 和 4 的两个值，代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。\n",
    "最后，对于每个下标 i ，都有 nums1[i] != nums2[i] 。总代价为 10 。\n",
    "还有别的交换值的方法，但是无法得到代价和小于 10 的方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>\n",
    "实现目标的一种方法为：\n",
    "- 交换下标为 2 和 3 的两个值，代价为 2 + 3 = 5 。现在 nums1 = [2,2,1,2,3] 。\n",
    "- 交换下标为 1 和 4 的两个值，代价为 1 + 4 = 5 。现在 nums1 = [2,3,1,2,2] 。\n",
    "总代价为 10 ，是所有方案中的最小代价。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums1 = [1,2,2], nums2 = [1,2,2]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>\n",
    "不管怎么操作，都无法满足题目要求。\n",
    "所以返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums1[i], nums2[i] &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-total-cost-to-make-arrays-unequal](https://leetcode.cn/problems/minimum-total-cost-to-make-arrays-unequal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-total-cost-to-make-arrays-unequal](https://leetcode.cn/problems/minimum-total-cost-to-make-arrays-unequal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n[1,2,3,4,5]', '[2,2,2,1,3]\\n[1,2,2,3,3]', '[1,2,2]\\n[1,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        #copy\n",
    "        ans = swapcnt = modecnt = mode =0\n",
    "        cnt = [0] * (len(nums1) +1)\n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if x == y:\n",
    "                ans += i \n",
    "                swapcnt += 1\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] >modecnt:\n",
    "                    modecnt,mode = cnt[x],x\n",
    "        \n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if modecnt *2 <= swapcnt:\n",
    "                break\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ans += i\n",
    "                swapcnt += 1\n",
    "        return ans if modecnt*2<= swapcnt else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # n = len(nums)\n",
    "        # dp = [0] * (n + 1)\n",
    "        # for i in range(0, n + 1):\n",
    "        #     if nums1[i] == nums2[i]:\n",
    "        #         for j in range(i):\n",
    "        #             if nums1[j] != nums1[i]:\n",
    "        #                 nums1[j], nums1[i] = nums1[i], nums1[j]\n",
    "        #                 dp[i] = dp[i -1] + j + i\n",
    "        #                 break\n",
    "            \n",
    "        #     else:\n",
    "        #         dp[i] = dp[i -1]\n",
    "\n",
    "        ans = swap_cnt = mode_cnt = mode = 0\n",
    "        cnt = [0] * (len(nums1) + 1)\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if x == y:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] > mode_cnt:\n",
    "                    mode_cnt, mode = cnt[x], x\n",
    "\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if mode_cnt * 2 <= swap_cnt: break\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "        return ans if mode_cnt * 2 <= swap_cnt else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = swap_cnt = mode_cnt = mode = 0\n",
    "        cnt = [0] * (len(nums1) + 1)\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if x == y:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] > mode_cnt:\n",
    "                    mode_cnt, mode = cnt[x], x\n",
    "\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if mode_cnt * 2 <= swap_cnt: break\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "        return ans if mode_cnt * 2 <= swap_cnt else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = swap_cnt = mode_cnt = mode = 0\n",
    "        cnt = [0] * (len(nums1) + 1)\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if x == y:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] > mode_cnt:\n",
    "                    mode_cnt, mode = cnt[x], x\n",
    "\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if mode_cnt * 2 <= swap_cnt: break\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "        return ans if mode_cnt * 2 <= swap_cnt else -1\n",
    "\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = swap_cnt = mode_cnt = mode = 0\n",
    "        cnt = [0] * (len(nums1) + 1)\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if x == y:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] > mode_cnt:\n",
    "                    mode_cnt, mode = cnt[x], x\n",
    "\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if mode_cnt * 2 <= swap_cnt: break\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "        return ans if mode_cnt * 2 <= swap_cnt else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "       n=len(nums1) \n",
    "       ans=s=m1=m=0\n",
    "       c=[0]*(n+1)\n",
    "       for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "          if x==y:\n",
    "             ans+=i\n",
    "             s+=1\n",
    "             c[x]+=1\n",
    "             if c[x]>m1:\n",
    "                m1,m=c[x],x\n",
    "       for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "           if m1*2<=s:\n",
    "               break\n",
    "           if x!= y and x!=m and y!=m:\n",
    "             ans+=i\n",
    "             s+=1\n",
    "       return ans if m1*2<=s else -1                      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = swap_cnt = mode_cnt = mode = 0\n",
    "        cnt = [0] * (len(nums1) + 1)\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if x == y:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] > mode_cnt:\n",
    "                    mode_cnt, mode = cnt[x], x\n",
    "\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if mode_cnt * 2 <= swap_cnt: break\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "        return ans if mode_cnt * 2 <= swap_cnt else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = swap_cnt = mode_cnt = mode = 0\n",
    "        cnt = [0] * (len(nums1) + 1)\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if x == y:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] > mode_cnt:\n",
    "                    mode_cnt, mode = cnt[x], x\n",
    "\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if mode_cnt * 2 <= swap_cnt: break\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "        return ans if mode_cnt * 2 <= swap_cnt else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = swap_cnt = mode_cnt = mode = 0\n",
    "        cnt = [0] * (len(nums1) + 1)\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if x == y:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "                cnt[x] += 1\n",
    "                if cnt[x] > mode_cnt:\n",
    "                    mode_cnt, mode = cnt[x], x\n",
    "\n",
    "        for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "            if mode_cnt * 2 <= swap_cnt: break\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ans += i\n",
    "                swap_cnt += 1\n",
    "        return ans if mode_cnt * 2 <= swap_cnt else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "       ans = swap_cnt = mode_cnt = mode = 0\n",
    "       cnt = [0] * (len(nums1) + 1)\n",
    "       for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "           if x == y:\n",
    "               ans += i\n",
    "               swap_cnt += 1\n",
    "               cnt[x] += 1\n",
    "               if cnt[x] > mode_cnt:\n",
    "                   mode_cnt, mode = cnt[x], x\n",
    "\n",
    "\n",
    "       for i, (x, y) in enumerate(zip(nums1, nums2)):\n",
    "           if mode_cnt * 2 <= swap_cnt: break\n",
    "           if x != y and x != mode and y != mode:\n",
    "               ans += i\n",
    "               swap_cnt += 1\n",
    "       return ans if mode_cnt * 2 <= swap_cnt else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, A: List[int], B: List[int]) -> int:\n",
    "        dif, cnt = [], [0] + [0] * (N := len(A))\n",
    "        hi = hc = tot = res = 0\n",
    "        for i, (a, b) in enumerate(zip(A, B)):\n",
    "            if a == b:\n",
    "                res += i\n",
    "                tot += 1\n",
    "                cnt[a] += 1\n",
    "                if cnt[a] > hc:\n",
    "                    hi, hc = a, cnt[a]\n",
    "            else:\n",
    "                dif.append(i)\n",
    "        if (c := hc + hc - tot) > 0:\n",
    "            i, n = 0, len(dif)\n",
    "            for _ in range(c):\n",
    "                while i < n and hi in (A[dif[i]], B[dif[i]]): i += 1\n",
    "                if i == n: return -1\n",
    "                res += dif[i]\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        mode = 0\n",
    "        mode_cnt = 0\n",
    "        swap_cnt = 0\n",
    "        res = 0\n",
    "        d = dict()\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                res += i\n",
    "                swap_cnt += 1\n",
    "                if nums1[i] in d:\n",
    "                    d[nums1[i]] += 1\n",
    "                else:\n",
    "                    d[nums1[i]] = 1\n",
    "                if d[nums1[i]] > mode_cnt:\n",
    "                    mode_cnt = d[nums1[i]]\n",
    "                    mode = nums1[i]\n",
    "        for i in range(n):\n",
    "            if mode_cnt * 2 > swap_cnt:\n",
    "                if nums1[i] != nums2[i] and nums1[i] != mode and nums2[i] != mode:\n",
    "                    res += i\n",
    "                    swap_cnt += 1\n",
    "        if mode_cnt * 2 <= swap_cnt:\n",
    "            return res\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "\n",
    "        ret = 0\n",
    "        swap_cnt = 0\n",
    "        mode_cnt = 0\n",
    "        mode = 0\n",
    "\n",
    "        cnts = defaultdict(int)\n",
    "\n",
    "        for i in range(n):\n",
    "            x, y = nums1[i], nums2[i]\n",
    "\n",
    "            if x == y:\n",
    "                ret += i\n",
    "                swap_cnt += 1\n",
    "                cnts[x] += 1\n",
    "\n",
    "                if cnts[x] > mode_cnt:\n",
    "                    mode = x\n",
    "                    mode_cnt = cnts[x]\n",
    "\n",
    "        if mode_cnt * 2 <= swap_cnt:\n",
    "            return ret\n",
    "\n",
    "        for i in range(n):\n",
    "            x, y = nums1[i], nums2[i]\n",
    "\n",
    "            if x != y and x != mode and y != mode:\n",
    "                ret += i\n",
    "                swap_cnt += 1\n",
    "\n",
    "            if mode_cnt * 2 <= swap_cnt:\n",
    "                return ret\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        C = Counter()\n",
    "        neqs = []\n",
    "        TC = res = 0\n",
    "\n",
    "        for i, (n1, n2) in enumerate(zip(nums1, nums2)):\n",
    "            if n1 == n2:\n",
    "                C[n1] += 1\n",
    "                TC += 1\n",
    "                res += i\n",
    "            else:\n",
    "                neqs.append(i)\n",
    "        if not C: return 0\n",
    "        x, xn = C.most_common(1)[0]\n",
    "        otherN = TC - xn\n",
    "        if xn > otherN:\n",
    "            cnt = xn - otherN\n",
    "            if len(neqs) < cnt: return -1\n",
    "            for i in neqs:\n",
    "                if nums1[i] != x and nums2[i] != x:\n",
    "                    cnt -= 1\n",
    "                    res += i\n",
    "                    if not cnt: return res\n",
    "            return -1\n",
    "        else:\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        cnt=Counter()\n",
    "        max_s=0\n",
    "        max_mode=0\n",
    "        ans=0\n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if x==y:\n",
    "                ans+=i\n",
    "                max_s+=1\n",
    "                cnt[x]+=1\n",
    "                if cnt[x]>max_mode:\n",
    "                    max_mode=cnt[x]\n",
    "                    mode=x  \n",
    "        if max_mode*2<=max_s:return ans\n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if max_mode*2<=max_s:break  \n",
    "            if x!=mode and y!=mode and x!=y:\n",
    "                ans+=i\n",
    "                # max_s+=1\n",
    "                max_mode-=1\n",
    "                max_s-=1\n",
    "        return ans if max_mode*2<=max_s else -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        cnt=Counter()\n",
    "        max_s=0\n",
    "        max_mode=0\n",
    "        ans=0\n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if x==y:\n",
    "                ans+=i\n",
    "                max_s+=1\n",
    "                cnt[x]+=1\n",
    "                if cnt[x]>max_mode:\n",
    "                    max_mode=cnt[x]\n",
    "                    mode=x  \n",
    "        if max_mode*2<=max_s:return ans\n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if max_mode*2<=max_s:break  \n",
    "            if x!=mode and y!=mode and x!=y:\n",
    "                ans+=i\n",
    "                max_s+=1\n",
    "        return ans if max_mode*2<=max_s else -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        t=0\n",
    "        cnt=collections.Counter()\n",
    "        ans=0\n",
    "        swap_cnt=0\n",
    "        mx=0\n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if x==y:\n",
    "                ans+=i \n",
    "                cnt[x]+=1\n",
    "                swap_cnt+=1\n",
    "                if cnt[x]>mx:\n",
    "                    mx=cnt[x]\n",
    "                    t=x\n",
    "        if mx*2<=swap_cnt:\n",
    "            return ans\n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if mx*2<=swap_cnt:\n",
    "                break\n",
    "            if x!=y and x!=t and y!=t:\n",
    "                swap_cnt+=1\n",
    "                ans+=i\n",
    "        if mx*2<=swap_cnt:\n",
    "            return ans\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        cnt = Counter()\n",
    "        tot = 0 \n",
    "        ans = 0 \n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                cnt[nums1[i]] += 1\n",
    "                tot += 1\n",
    "                ans += i \n",
    "        m = -1 \n",
    "        for k in cnt:\n",
    "            if m == -1 or cnt[k] > cnt[m]:\n",
    "                m = k \n",
    "        if cnt[m] <= tot // 2:\n",
    "            return ans \n",
    "        d = 2 * cnt[m] - tot \n",
    "        for i in range(n):\n",
    "            if nums1[i] != nums2[i] and nums1[i] != m and nums2[i] != m:\n",
    "                d -= 1\n",
    "                ans += i \n",
    "                if d == 0:\n",
    "                    return ans \n",
    "        return -1 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        \n",
    "        # 标记数组，标记nums1和nums2在相同位置上是否有相同的数字\n",
    "        vis = [False] * n\n",
    "        \n",
    "        # 记录交换的总开销\n",
    "        res = 0\n",
    "        # 记录需要交换的数字的数量\n",
    "        cnt = 0\n",
    "        \n",
    "        # 使用哈希表存储在相同位置上相同的数字及其出现的次数\n",
    "        h = Counter()\n",
    "        m = 0\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                vis[i] = True\n",
    "                res += i\n",
    "                cnt += 1\n",
    "                h[nums1[i]] += 1\n",
    "                if h[nums1[i]] > h[m]:\n",
    "                    m = nums1[i]\n",
    "        \n",
    "        # 如果需要交换的数字数量小于出现次数最多的数字的两倍，则尝试交换\n",
    "        if cnt < h[m] * 2:\n",
    "            for i in range(n):\n",
    "                if not vis[i] and nums1[i] != m and nums2[i] != m:\n",
    "                    res += i\n",
    "                    cnt += 1\n",
    "                    if cnt >= h[m] * 2:\n",
    "                        break\n",
    "        \n",
    "        # 如果所有需要交换的数字都能成功交换，则返回总开销，否则返回-1\n",
    "        return res if cnt >= h[m] * 2 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        counter = collections.Counter()\n",
    "        swap = []\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                swap.append(i)\n",
    "                counter[nums1[i]] += 1 \n",
    "        if not swap:\n",
    "            return 0\n",
    "        maxNum, maxCnt = counter.most_common(1)[0]\n",
    "        if len(swap) >= maxCnt * 2:\n",
    "            return sum(swap)\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i] or nums1[i] == maxNum or nums2[i] == maxNum:\n",
    "                continue \n",
    "            swap.append(i)\n",
    "            if len(swap) >= maxCnt * 2:\n",
    "                return sum(swap)\n",
    "        return - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        counter = collections.Counter()\n",
    "        swap = []\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                swap.append(i)\n",
    "                counter[nums1[i]] += 1 \n",
    "        if not swap:\n",
    "            return 0\n",
    "        maxNum, maxCnt = counter.most_common(1)[0]\n",
    "        if len(swap) >= maxCnt * 2:\n",
    "            return sum(swap)\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i] or nums1[i] == maxNum or nums2[i] == maxNum:\n",
    "                continue \n",
    "            swap.append(i)\n",
    "            if len(swap) >= maxCnt * 2:\n",
    "                return sum(swap)\n",
    "        return - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        swap = []\n",
    "        counter = collections.Counter()\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                swap.append(i)\n",
    "                counter[nums1[i]] += 1 \n",
    "        if not swap:\n",
    "            return 0\n",
    "        maxNum, maxCnt = counter.most_common(1)[0]\n",
    "        if maxCnt * 2 <= len(swap):\n",
    "            return sum(swap)\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i] or nums1[i] == maxNum or nums2[i] == maxNum:\n",
    "                continue \n",
    "            swap.append(i)\n",
    "            if maxCnt * 2 <= len(swap):\n",
    "                return sum(swap)\n",
    "        return - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        ans = 0\n",
    "        ind = []\n",
    "        cnt= Counter()\n",
    "        for i in range(n):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                cnt[nums1[i]] += 1\n",
    "                ind.append(i)\n",
    "        if not ind:\n",
    "            return ans\n",
    "        ceil =max(cnt.values())\n",
    "        if ceil*2 <= len(ind):\n",
    "            return sum(ind)\n",
    "        num = [x for x in cnt if cnt[x]==ceil][0]\n",
    "        for i in range(n):\n",
    "            if nums1[i] == num or nums2[i] == num:\n",
    "                continue\n",
    "            if nums1[i] == nums2[i]:\n",
    "                continue\n",
    "            ind.append(i)\n",
    "            if ceil*2<=len(ind):\n",
    "                return sum(ind)\n",
    "        return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
